package 题目集.动态规划.背包问题;

import java.util.ArrayList;
import java.util.List;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/maximum-value-of-k-coins-from-piles/description/
 * 一张桌子上总共有 n 个硬币 栈 。每个栈有 正整数 个带面值的硬币。 每一次操作中，你可以从任意一个栈的 顶部 取出 1
 * 个硬币，从栈中移除它，并放入你的钱包里。 给你一个列表 piles ，其中 piles[i] 是一个整数数组，分别表示第 i 个栈里 从顶到底
 * 的硬币面值。同时给你一个正整数 k ，请你返回在 恰好 进行 k 次操作的前提下，你钱包里硬币面值之和 最大为多少 。
 */
public class ch07_从栈中取出k个硬币的面额和 {
	/**
	 * dp[i][j]：有i个栈，j次机会能选出的最大值。 设第i个栈有数据a1,a2,a3...an
	 * dp[i][j]=max(dp[i-1][j],dp[i-1][j-1]+a1,dp[i-1][j-2]+a1+a2,...,dp[i-1][j-n]+sum(a1~an));
	 */
	public int maxValueOfCoins(List<List<Integer>> piles, int k) {
		int[][] dp = new int[2][k + 1];
		int pre, cur = 0;
		int size = piles.size();
		for (int i = 0; i < size; i++) {
			pre = cur;
			cur = (cur + 1) % 2;
			List<Integer> list = piles.get(i);
			int curSize = list.size();
			int[] sum = new int[curSize + 1];
			for (int z = 1; z <= curSize; z++) {
				sum[z] = sum[z - 1] + list.get(z - 1);
			}
			for (int j = 1; j <= k; j++) {
				for (int z = 0; z <= j && z <= curSize; z++) {
					dp[cur][j] = Math.max(dp[cur][j], dp[pre][j - z] + sum[z]);
				}
			}
		}
		return dp[cur][k];
	}

	@Test
	public void test() {
		List<List<Integer>> arrgs = new ArrayList<>();
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(100);
			}
		});
		arrgs.add(new ArrayList<Integer>() {
			{
				add(1);
				add(1);
				add(1);
				add(1);
				add(1);
				add(1);
				add(700);
			}
		});
		int k=7;
		int res = maxValueOfCoins(arrgs, k);
		System.out.println(res);
	}
}
